﻿
public class Solution54
{
    IList<int> result;
    public IList<int> SpiralOrder(int[][] matrix)
    {

        result=new List<int>();
        int m=matrix.Length;
        int n = matrix[0].Length;
        int left = 0;
        int right = n - 1;
        int top = 0;
        int bot = m - 1;
      
        DFS(matrix, left, right, top, bot);

        return result;

    }

    private void DFS(int[][] matrix, int left, int right, int top, int bot)
    {



        if (left > right) return;    
        if (top > bot) return;

       
            //最上面
            for (int i = left; i <= right; i++)
            {//第一行遍历完,满足只有一行的情况，top==bot


                result.Add(matrix[top][i]);



            }
            //最右
            for (int i = top + 1; i <= bot; i++)//最后一列遍历完,满足只有一列的情况，left==right
            {


                result.Add(matrix[i][right]);


            }
           


        if (left < right && top < bot)
        {
            //最下面
            for (int i = right - 1; i >= left; i--)
            {


                result.Add(matrix[bot][i]);


            }
            //最左面
            for (int i = bot - 1; i > top; i--)
            {


                result.Add(matrix[i][left]);


            }
        }

        DFS(matrix, left+1, right-1, top+1, bot-1);

    }
}
class Program54
{


    static void Main54(string[] args)
    {
        int[][] matrix = matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
        Solution54 solution = new Solution54();
        IList<int> res= solution.SpiralOrder(matrix);
        for (int i = 0; i < res.Count; i++)
        {
            Console.WriteLine(res[i]);

        }



    }
}
